package com.sise.Array;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 *      剑指 Offer 40. 最小的 k 个数
 *
 *      输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 *
 *      输入：arr = [3,2,1], k = 2
 *      输出：[1,2] 或者 [2,1]
 *
 *      题解：
 *      使用大根堆，先将前 k 个数都放在大根堆中，从 k+1 个数开始，比较 arr[i] 与 大根堆的堆顶，
 *      如果小于堆顶元素，那么就将 堆顶元素删除，将 arr[i] 添加进去。等到所有数字都遍历完毕之后，那么就将其输入
 */
public class _offer_40_getLeastNumbers {
    public int[] getLeastNumbers(int[] arr, int k) {

        int[] vec = new int[k];
        if (k == 0){
            return vec;
        }

        // 建立大根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer num1, Integer num2){
                return num2 - num1;
            }
        });

        for (int i = 0; i < k; i++){
            queue.offer(arr[i]);
        }

        for (int i = k; i < arr.length; ++i){
            if (queue.peek() > arr[i]){
                queue.poll();
                queue.offer(arr[i]);
            }
        }

        for (int i = 0; i < k; ++i){
            vec[i] = queue.poll();
        }
        return vec;
    }
}
